import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @作者 钟先崟
 * @时间 2023-02-15 18:14
 * @说明 1944. 队列中可以看到的人数
 * 有 n 个人排成一个队列，从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数 互不相同，heights[i] 表示第 i 个人的高度。
 * 一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的，第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]) 。
 * 请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。
 */
public class Solution {
    public static void main(String[] args) {
//        int[] heights = new int[]{10, 6, 8, 5, 11, 9};
        int[] heights = new int[]{5, 1, 2, 3, 10};
        int[] look = canSeePersonsCount(heights);
        for (Integer x : look) {
            System.out.print(x + " ");
        }
    }

    /**
     * 执行用时：
     * 128 ms
     * , 在所有 Java 提交中击败了
     * 34.68%
     * 的用户
     * 内存消耗：
     * 60 MB
     * , 在所有 Java 提交中击败了
     * 52.03%
     * 的用户
     * @param heights
     * @return
     */
    public static int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        int[] ans = new int[n];
        // 单调递减栈，保存右边的可能看到的人的下标值
        Stack<Integer> monotoneStack = new Stack<>();
        // 倒序遍历 能看到多少只与右边的数值有关系
        for (int i = n - 1; i >= 0; i--) {
            while (!monotoneStack.isEmpty()) {
                ans[i]++;
                // 比单调栈中当前值小，证明看不到这个值右边的了，结束比较
                if (heights[i] <= heights[monotoneStack.peek()]) {
                    break;
                }
                // 比单调栈中的当前值大，左边的人肯定都看不到这个值之后的人了
                // 出栈，接着循环
                monotoneStack.pop();
            }
            // 单调栈中放入下标，保证单调递减（栈为空或者h[i]<h[j]）
            monotoneStack.push(i);
        }
        return ans;
//        int[] look = new int[heights.length];
//        int max;
//        for (int i = 0; i < heights.length; i++) {
//            max = 0;
//            for (int j = i + 1; j < heights.length; j++) {
//                if (heights[j] > max && max < heights[i]) {
//                    look[i]++;
//                    max = heights[j];
//                } else if (max >= heights[i])
//                    break;
//            }
//        }
//        return look;
    }
}
